package baseclass.d_list;


import utils.ListNode;
import utils.ListUtil;

import java.util.LinkedList;
import java.util.List;

/**
 *    链表的荷兰国旗问题：
 *    方式1：遍历链表，把节点依次放入一个数组,然后用数组解决，再把数组的链表重新连起来。
 *          笔试就该这么做。空间o(n)。当然数组中的荷兰问题是不稳定的
 *    方式2：
 *    	   准备三个引用，less，equal，more。遍历[遍历一个要释放一个，让其next指向null]，
 * 		依次把小于、等于、大于的节点放在 less、equal、more的引用上
 *          最后把这三个引用重新连接。
 * 		用到的空间复杂度是o(1)【在原链表基础上进行引用的连接】,但是是稳定的!
 *       注意要有的区域为空的判断。
 * @date 2020/2/28 0:15
 */
public class Code04_NetherFlagList {
    /**
     * 方式1：遍历把数据存到容器，然后重新把链表赋值。
     * 时空都是O(n),适合OJ。
     */
    public static ListNode listPartition1(ListNode head, int target) {
        if(head == null || head.next == null) return head;
        ListNode p = head;
        int len = 1;
        while (p.next != null){
            p = p.next;
            len ++;
        }
        ListNode[] nodes = new ListNode[len];
        p = head;
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = p;
            p = p.next;
        }
        partition(nodes,target);
        //把node连起来
        p = head = nodes[0];
        for (int i = 1; i < nodes.length ; i++) {
            p.next = nodes[i];
            p = p.next;
        }
        //注意这里一定要处理 ，不然可能会形成环
        nodes[nodes.length - 1].next = null;
        return nodes[0];
    }
    /**
     * 方式2：用链表先存 < x，再存 = x，最后存 > x
     */
    public static ListNode listPartition2(ListNode head, int target) {
        if(head == null || head.next == null) return head;
        List<ListNode> list = new LinkedList<>();
        ListNode p = head;
        while (p != null){
            if(p.val < target)
                list.add(p);
            p = p.next;
        }
         p = head;
        while (p != null){
            if(p.val == target)
                list.add(p);
            p = p.next;
        }
        p = head;
        while (p != null){
            if(p.val > target)
                list.add(p);
            p = p.next;
        }
        head = p = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            p.next = list.get(i);
            p = p.next;
        }
        p.next = null;
        return head;
    }

    /**
     * 方式3：准备3个指针，分别指向more，less,equal。
     * 遍历时分别把三块区域各自穿起来。最后串起三块区域
     */
    public static ListNode listPartition3(ListNode head, int target) {
        if(head == null || head.next == null) return head;
        ListNode lhead = null;
        ListNode ltail = null;
        ListNode ehead = null;
        ListNode etail = null;
        ListNode mhead = null;
        ListNode mtail = null;
        ListNode p = head;
        while (p != null){
            //记录next
            ListNode next = p.next;
            //一定要把p断开
            p.next = null;
            if(p.val < target){
                //如果是第一次连接
                if(lhead == null){
                    lhead = ltail = p;
                }else {
                    ltail.next = p;
                    ltail = ltail.next;
                }
            }else if(p.val == target){
                if(ehead == null){
                    ehead = etail = p;
                }else {
                    etail.next = p;
                    etail = etail.next;
                }
            }else {
                if(mhead == null){
                    mhead = mtail = p;
                }else {
                    mtail.next = p;
                    mtail = mtail.next;
                }
            }
            p = next;
        }

        //合并三块区域

        //合并前两块
        //如果小 的区域 存在，其tail和 等 的区域头连接，即使ehead为空也可以
        if(ltail != null){
            ltail.next = ehead;
        }
        //合并最后一块

        //如果中间区域存在
        if(etail != null){
            etail.next = mhead;
        }else if(ltail != null){//如果中间区域不存在
            ltail.next = mhead;
        }
        return lhead == null ?(
                ehead == null ? mhead : ehead
                ) : lhead;
    }


    private static void partition(ListNode[] nodes, int target) {
        int less = -1;
        int more = nodes.length;
        int p = 0;
        while (p < more){
            if(nodes[p].val <target){
                swap(nodes,++less,p++);
            }else if(nodes[p].val > target){
                swap(nodes,--more,p);
            }else {
                p++;
            }
        }
    }

    private static void swap(ListNode[] nodes, int i, int j) {
        ListNode temp = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = temp;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(7);
        head1.next = new ListNode(9);
        head1.next.next = new ListNode(1);
        head1.next.next.next = new ListNode(8);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(2);
        head1.next.next.next.next.next.next = new ListNode(5);
        ListUtil.printLinkedList(head1);
        /*head1 = listPartition1(head1, 5);
        ListUtil.printLinkedList(head1);*/
        head1 = listPartition2(head1, 5);
        ListUtil.printLinkedList(head1);
        head1 = listPartition2(head1, 8);
        ListUtil.printLinkedList(head1);

    }
}
